require 'set'
require './PDA.rb'

class NPDARulebook < Struct.new(:rules)
    def next_configurations(configurations, character)
        configurations.flat_map { |config| follow_rules_for(config, character)}.to_set
    end

    def follow_rules_for(configuration, character)
        rules_for(configuration, character).map { |rule|
            rule.follow(configuration)
        }
    end

    def rules_for(configuration, character)
        rules.select {|rule| rule.applies_to?(configuration, character)}
    end

    def follow_free_moves(configurations)
        more_configurations = next_configurations(configurations, nil)
        if more_configurations.subset?(configurations)
            configurations
        else
            follow_free_moves(configurations + more_configurations)
        end
    end
end

class NPDA < Struct.new(:current_configurations, :accept_states, :rulebook)
    def accepting?
        current_configurations.any? { |config| accept_states.include?(config.state)}
    end

    def read_character(character)
        self.current_configurations = 
        rulebook.next_configurations(current_configurations, character)
    end

    def read_string(string)
        string.chars.each do |character|
            read_character(character)
        end
    end

    def current_configurations
        rulebook.follow_free_moves(super)
    end
end

class NPDADesign < Struct.new(:start_state, :bottom_character, :accept_states, :rulebook)
    def accepts?(string)
        to_npda.tap { |npda| npda.read_string(string) }.accepting?
    end

    def to_npda
        start_stack = Stack.new([bottom_character])
        start_configuration = PDAConfiguration.new(start_state, start_stack)
        NPDA.new(Set[start_configuration], accept_states, rulebook)
    end
end